package com.sh.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * 如何将中缀表达式转成逆波兰表达式
 *具体步骤：
 * 1、
 *
 *
 */

/**
 * @ClassName PolandNotation
 * @Description 逆波兰计算器 后缀表达式求值
 * @Author yaoqiang
 * @Date 2020/11/6 13:44
 * @Version 1.0
 */
public class PolandNotation {
    public static void main(String[] args) {
        /***
         * 先定义一个逆波兰表达式 (3+4)*5-6., (30+4)*5-6
         * 为了方便，逆波兰表达式中的数字和符号使用空格隔开
         * 思路:
         *  1、先将suffixExpression装入到ArrayList中
         *  2、将ArrayList传给一个方法，遍历arrayList就行使用配合stack完成计算
         */
        String suffixExpression="30 4 + 5 * 6 -";
        //将一个逆波兰表达式，依次将数字和运算符放入到ArrayList
        List<String> list=getListString(suffixExpression);
        int result=  calculate(list);
        System.out.println(result);
    }

    /**
     * uffixExpression装入到ArrayList
     * @param suffixExpression
     * @return
     */
    public static List<String> getListString(String suffixExpression){
        String[] split=suffixExpression.split(" ");
        List<String> list=new ArrayList<String>();
        for (String ele:split){
            list.add(ele);
        }
        return list;
    }

    /**
     * 完成逆波兰计算器的表达式运算
     * 1、从左到右扫描，将3和4压入栈
     * 遇到+弹出4和3，计算出3+4的值，得7，将7放入栈
     * 5入栈
     * 遇到*弹出5和7，急速三得35，压入栈
     * 6入栈
     * 最后是-，计算出35-6，得29，
     * @param ls
     * @return
     */
    public static  int calculate(List<String> ls){
        //创建一个栈
        Stack<String> stack=new Stack<String>();
        //遍历list
        for (String item:ls){
            //这里使用正则表达式
            if (item.matches("\\d+")){
                //匹配多位数，入栈
                stack.push(item);
            }else {
                //pop出两个数，并运算，用当前扫描的结果
              int num2= Integer.parseInt(stack.pop());
                int num1= Integer.parseInt(stack.pop());
                int res=0;
                if (item.equals("+")){
                    res=num1+num2;
                }else if (item.equals("-")){
                    res=num1-num2;
                }else if (item.equals("*")){
                    res=num1*num2;
                }else if (item.equals("/")){
                    res=num1/num2;
                }else {
                    throw new RuntimeException("运算符有问题");
                }
                    stack.push(res+"");
            }
        }
        //最后在stack是运算结果
        return Integer.parseInt(stack.pop());
    }

}
